/*
 * malloc.c --- a general purpose kernel memory allocator for Linux.
 * 
 * Written by Theodore Ts'o (tytso@mit.edu), 11/29/91
 *
 * This routine is written to be as fast as possible, so that it
 * can be called from the interrupt level.
 *
 * Limitations: maximum size of memory we can allocate using this routine
 *	is 4k, the size of a page in Linux.
 *
 * The general game plan is that each page (called a bucket) will only hold
 * objects of a given size.  When all of the object on a page are released,
 * the page can be returned to the general free pool.  When malloc() is
 * called, it looks for the smallest bucket size which will fulfill its
 * request, and allocate a piece of memory from that bucket pool.
 *
 * Each bucket has as its control block a bucket descriptor which keeps 
 * track of how many objects are in use on that page, and the free list
 * for that page.  Like the buckets themselves, bucket descriptors are
 * stored on pages requested from get_free_page().  However, unlike buckets,
 * pages devoted to bucket descriptor pages are never released back to the
 * system.  Fortunately, a system should probably only need 1 or 2 bucket
 * descriptor pages, since a page can hold 256 bucket descriptors (which
 * corresponds to 1 megabyte worth of bucket pages.)  If the kernel is using 
 * that much allocated memory, it's probably doing something wrong.  :-)
 *
 * Note: malloc() and free() both call get_free_page() and free_page()
 *	in sections of code where interrupts are turned off, to allow
 *	malloc() and free() to be safely called from an interrupt routine.
 *	(We will probably need this functionality when networking code,
 *	particularily things like NFS, is added to Linux.)  However, this
 *	presumes that get_free_page() and free_page() are interrupt-level
 *	safe, which they may not be once paging is added.  If this is the
 *	case, we will need to modify malloc() to keep a few unused pages
 *	"pre-allocated" so that it can safely draw upon those pages if
 * 	it is called from an interrupt routine.
 *
 * 	Another concern is that get_free_page() should not sleep; if it 
 *	does, the code is carefully ordered so as to avoid any race 
 *	conditions.  The catch is that if malloc() is called re-entrantly, 
 *	there is a chance that unecessary pages will be grabbed from the 
 *	system.  Except for the pages for the bucket descriptor page, the 
 *	extra pages will eventually get released back to the system, though,
 *	so it isn't all that bad.
 */

#include <linux/kernel.h>
#include <linux/mm.h>
#include <asm/system.h>

// 分配描述结构
// 用于管理当前分配的存储页空间，空闲块链表
struct bucket_desc {	/* 16 bytes */
	void			*page;					// 整个空闲区域的起始地址
	struct bucket_desc	*next;				// 下一个描述符
	void			*freeptr;				// 空闲的块链表
	unsigned short		refcnt;				// 记录当前已经分配出去了多少块
	unsigned short		bucket_size;		// 块大小
};

// 桶分配的目录项
struct _bucket_dir {	/* 8 bytes */
	int			size;
	struct bucket_desc	*chain;
};

/*
 * 下面是我们存放第一个给定大小存储桶描述符指针的地方。
 *
 * 如果Linux 内核分配了许多指定大小的对象，那么我们就希望将该指定的大小加到
 * 该列表(链表)中，因为这样可以使内存的分配更有效。但是，因为一页完整内存页面
 * 必须用于列表中指定大小的所有对象，所以需要做总数方面的测试操作。
 */
// 可能看到，只能实现以下列整数个单位字节的内存分配，也就是说分配出去的实际有多的。
struct _bucket_dir bucket_dir[] = {
	{ 16,	(struct bucket_desc *) 0},
	{ 32,	(struct bucket_desc *) 0},
	{ 64,	(struct bucket_desc *) 0},
	{ 128,	(struct bucket_desc *) 0},
	{ 256,	(struct bucket_desc *) 0},
	{ 512,	(struct bucket_desc *) 0},
	{ 1024,	(struct bucket_desc *) 0},
	{ 2048, (struct bucket_desc *) 0},
	{ 4096, (struct bucket_desc *) 0},	   // 因为每次申请内存，最多4KB，不能申请连续多个4KB
	{ 0,    (struct bucket_desc *) 0}};   /* End of list marker */

/*
 * This contains a linked list of free bucket descriptor blocks
 */
// 空闲bucket_desc链表，每次需要分配但又为空的时候，就分配一页内存，划分成很多个
// 然后构成链表，方便后续进行分配
struct bucket_desc *free_bucket_desc = (struct bucket_desc *) 0;

/*
 * This routine initializes a bucket description page.
 */
static inline void init_bucket_desc()
{
	struct bucket_desc *bdesc, *first;
	int	i;
	
	// 分配一页内容，用于bucket_desc的表项的分配
	// 系统中没有动态分配函数，只能按页分配，所以这里使用了页分配的方式，分配一页
	first = bdesc = (struct bucket_desc *) get_free_page();
	if (!bdesc)
		panic("Out of memory in init_bucket_desc()");

	// 将这一页内存划分成很多个bucket_desc，然后建立起相应的链表
	// 从第一个开始，不断建立成链表
	for (i = PAGE_SIZE/sizeof(struct bucket_desc); i > 1; i--) {
		bdesc->next = bdesc+1;
		bdesc++;
	}
	/*
	 * 这是在最后处理的，目的是为了避免在get_free_page()睡眠时该子程序又被
	 * 调用而引起的竞争条件。
	 */
	// 这里实际上是将0给到next，也为free_bucket_desc初始值就是0
	 bdesc->next = free_bucket_desc;

	// 将free_bucket_desc指向第一个结点
	free_bucket_desc = first;
}

//// 分配动态内存函数。
// 参数：len - 请求的内存块长度。
// 返回：指向被分配内存的指针。如果失败则返回NULL。
void *malloc(unsigned int len)
{
	struct _bucket_dir	*bdir;
	struct bucket_desc	*bdesc;
	void			*retval;

/*
 * 首先我们搜索存储桶目录bucket_dir 来寻找适合请求的桶大小。
 */
// 搜索存储桶目录，寻找适合申请内存块大小的桶描述符链表。如果目录项的桶字节
// 数大于请求的字节数，就找到了对应的桶目录项。
	for (bdir = bucket_dir; bdir->size; bdir++)
		// 找到一个空间比要求的>=的表项即可。
		// 注意，这里可能没有所需的内存，因此在下面会进行分配。
		if (bdir->size >= len)
			break;
	
	// 如果为0，即找不到。应当是要求大小太大了，超过4096KB，不能分配
	if (!bdir->size) {
		printk("malloc called with impossibly large argument (%d)\n",len);
		panic("malloc: bad arg");		// 原地死机的函数
	}
	/*
	 * Now we search for a bucket descriptor which has free space
	 */
	// 这块是通用的代码，进程、中断都可以使用，所以需要加以保护
	// 关中断，这样适用于中断处理函数中也能够调用。而是会挂起当前进程
	cli();	/* Avoid race conditions */
	for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) 
		// 遍历列表，看看描述符中是否有空闲的块，没有则跳出
		if (bdesc->freeptr)
			break;
	/*
	 * If we didn't find a bucket with free space, then we'll 
	 * allocate a new one.
	 */
	// 如果没有找到描述符有空闲的项列表
	// 则分配一个新的表项，并且构建一个新的描述符表
	if (!bdesc) {
		char		*cp;
		int		i;

		// 空闲链表为空，新创建一个链表，继续用于描述符的分配
		// 空闲的表项，即有分配的页，所有的内容都已经分配出去了
		if (!free_bucket_desc)	
			init_bucket_desc();

		// 取一个描述符
		bdesc = free_bucket_desc;
		free_bucket_desc = bdesc->next;
		
		// 字段初始化
		bdesc->refcnt = 0;
		bdesc->bucket_size = bdir->size;

		// 以下是分配一页内容，然后构造供分配的空闲存储块链表
		bdesc->page = bdesc->freeptr = (void *) (cp = get_free_page());		// 分配一页内容
		if (!cp)
			panic("Out of memory in kernel malloc()");
		/* Set up the chain of free objects */
		// 将这一页内存，建立成链表，加入到当前的描述符中，方便后续进行分配
		for (i=PAGE_SIZE/bdir->size; i > 1; i--) {
			// 使用每一个块的头部，放置一个指针，用于指向下一结点
			*((char **) cp) = cp + bdir->size;
			cp += bdir->size;
		}
// 最后一个对象开始处的指针设置为0(NULL)。
// 然后让该桶描述符的下一描述符指针字段指向对应桶目录项指针chain 所指的描述符，而桶目录的
// chain 指向该桶描述符，也即将该描述符插入到描述符链链头处。
		*((char **) cp) = 0;

		// 将新创建的描述符加入目录链
		bdesc->next = bdir->chain; /* OK, link it in! */
		bdir->chain = bdesc;
	}

	// 将空闲的项分配出来，然后freeptr前移？
	retval = (void *) bdesc->freeptr;
	bdesc->freeptr = *((void **) retval);

	// 增加描述符的索引，注意，不是块的索引！！！
	// 因为当前已经分配出去了一个块
	bdesc->refcnt++;

	// 开中断，取消保护
	sti();	/* OK, we're safe again */
	return(retval);
}

/*
 * 下面是释放子程序。如果你知道释放对象的大小，则free_s()将使用该信息加速
 * 搜寻对应桶描述符的速度。
 * 
 * 我们将定义一个宏，使得"free(x)"成为"free_s(x, 0)"。
 */
void free_s(void *obj, int size)
{
	void		*page;
	struct _bucket_dir	*bdir;
	struct bucket_desc	*bdesc, *prev;
	bdesc = prev = 0;
	/* Calculate what page this object lives in */
	// 获取分配的内存所在的页
	page = (void *)  ((unsigned long) obj & 0xfffff000);
	/* Now search the buckets looking for that page */

	// 遍历目录表，找到所在的页
	for (bdir = bucket_dir; bdir->size; bdir++) {
		prev = 0;
		/* If size is zero then this conditional is always false */
		// 大小不同，显示不合适。这里能回加快查找
		if (bdir->size < size)
			continue;

		// 找到了合适的目录项。进入该项时遍历
		for (bdesc = bdir->chain; bdesc; bdesc = bdesc->next) {
			// 每个描述符指向了一页内容，一页内容中的多页进行分配。
			// 因此，这里使用page进行判断，判断是否属于该描述符下，不属于显示不能在此释放
			if (bdesc->page == page) 
				goto found;
			prev = bdesc;
		}
	}

	// 没有找到，则死机。。。。
	panic("Bad address passed to kernel free_s()");
found:
	cli(); /* To avoid race conditions */

	// 插入空闲列表中
	*((void **)obj) = bdesc->freeptr;
	bdesc->freeptr = obj;

	// 引用计数-1，即所有的都已经释放回来，那么就需要回收空间了
	bdesc->refcnt--;		
	if (bdesc->refcnt == 0) {
		/*
		 * We need to make sure that prev is still accurate.  It
		 * may not be, if someone rudely interrupted us....
		 */
		if ((prev && (prev->next != bdesc)) ||			// 前一个非空，但下一个并不指向自己
		    (!prev && (bdir->chain != bdesc)))			// 前一个为空，但自己并不是目录表的开头
			// 说明这个pre可能由于某些原因出错，所以重新遍历列表，寻找正确的pre, 方便后面回收当前描述符
			for (prev = bdir->chain; prev; prev = prev->next)
				if (prev->next == bdesc)
					break;
		// 将描述符从链表中取出
		if (prev)		// 前一个非0
			prev->next = bdesc->next;		// 修改其后续结点指向下一个
		else {
			if (bdir->chain != bdesc)		// 如果为0，看看自己是不是当前，不是当前的明显有问题
				panic("malloc bucket chains corrupted");
			bdir->chain = bdesc->next;		// 将头指针指向自己后继
		}

		// 释放描述符所在的页
		free_page((unsigned long) bdesc->page);

		// 回收描述符
		bdesc->next = free_bucket_desc;
		free_bucket_desc = bdesc;
	}
	sti();
	return;
}

